{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Quantum Approximate Optimization Algorithm \n",
    "\n",
    "Qiskit has an implementation of the Quantum Approximate Optimization Algorithm [QAOA](https://qiskit.org/documentation/stubs/qiskit.aqua.algorithms.QAOA.html) and this notebook demonstrates using it for a graph partition problem.\n",
    "\n",
    "While QAOA can be directly used it often more convenient to use it in conjunction with the Optimization module. See the Optimization tutorials for more information."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import networkx as nx\n",
    "\n",
    "from qiskit import BasicAer\n",
    "from qiskit.aqua.algorithms import NumPyMinimumEigensolver\n",
    "from qiskit.optimization.applications.ising import graph_partition\n",
    "from qiskit.optimization.applications.ising.common import random_graph, sample_most_likely"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First we create a random graph and draw it so it can be seen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0. -5. -6.  0.]\n",
      " [-5.  0. -2.  5.]\n",
      " [-6. -2.  0.  4.]\n",
      " [ 0.  5.  4.  0.]]\n"
     ]
    }
   ],
   "source": [
    "num_nodes = 4\n",
    "w = random_graph(num_nodes, edge_prob=0.8, weight_range=10, seed=48)\n",
    "print(w)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "tags": [
     "nbsphinx-thumbnail"
    ]
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAcUAAAE1CAYAAACWU/udAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvNQv5yAAAIABJREFUeJzt3XlcVOXiBvBnhn1TwQUXcMclUzNzRQkhURRxS0NRNr1KZrZp5nWDa6b+vGWmlqUOiBvihqgggogLmlrmWoa74IIpisg2DDO/P0RumivM8J6Zeb6fz/1wY2bOeQDhmfc957xHptFoNCAiIiLIRQcgIiKSCpYiERFRKZYiERFRKZYiERFRKZYiERFRKZYiERFRKZYiERFRKZYiERFRKZYiERFRKZYiERFRKZYiERFRKZYiERFRKZYiERFRKZYiERFRKZYiERFRKZYiERFRKZYiERFRKZYiERFRKZYiERFRKZYiERFRKZYiERFRKZYiERFRKZYiERFRKVPRAZ5HqbyNGzdW4ObNFSguvg2NpgQmJrawt/eEs/NnsLVtKzoiEREZEJlGo9GIDvEkpTIL586Nx5072wHIoFYXPPEME8jlFrCyaoKmTRfC3r6HiJhERGRgJFeK+fnn8Ntv3VFcnA2g+IXPl8ut4OKyBHXqBOs+HBERGTRJlWJR0U388ktbFBf/BeDlY8nlVmjZci1q1hygu3BEZHA0Gg1ylblQa9SoYlEFchlPszB2kirFkyd9kJ2dCED1yq+Vy63Rtet1mJpW1X4wIjIYGo0G+67sw/yD85F4IREyyCCTyaAqUaGTUydMdp2Mvs36wlQu6VMuSEckU4pFRdfx88+NodEUlev1crkNGjeeCyen8VpORkSGIu1qGoZvHo7sgmzkKfOgecqMlJ25HcxNzPFD3x8wpNUQASlJJMnMFVy7trRCr1er85CRMR8S6XiqJB07dsRrr72GDh06oFWrVrh3794/nrNo0SJ07NgRHTp0wOnTpwWkJCmIPRuLnqt64mrOVTxQPnhqIQJArjIXdwruIDA2EP89+N9KTkmiSWZ+4ObNFeUeJT6iUmXjwYMTsLN7Q0upSOpycnKwadMmtGjRAkVFRbCxsXns8ePHj2Pr1q1QKBTIyMjA559/jg0bNvzjeWTYDmYchP9mfxSonjyT/dkKVAWYmToTjraOGNlmpA7TkZRIZqSoUmVXeBtqtQyXL/+Ky5cvIyMjAzdu3MCtW7eQnZ2NnJwc5OXlobCwECqViiNKA2JnZwdTU9OnFl10dDR8fX3x+uuvw9vbGxcvXkRWVpaAlCSKRqPB8E3DkV+c/8qvzS/OR+j2UOQp83SQjKRIMiNFtfrFl1+8SF5eHhYtmopffpkFlUqFkpKSZ34sKSmBXC6HiYkJTE1NX/jxZZ5T3o9S3bZcLodMJtPCT1d3TE1N0b9/f5iYmGDs2LEYM2bMY4+fP38eHh4eUKvVkMvlcHZ2xs2bN9G4cWNBiamy7b+6H3cK7pT79XLIsfbUWvyr/b+0mIqkSjKlaGJig5KS+xXahp2dHZYti4a9vfsLn6vRaKBWq59bni8qVm18fPL/FxYW6mTb5fmoVqthYmIimVL/9NNP4eDg8NjPMTExEbVq1cL9+/fRq1cvuLi4oEeP/y3moFKpygoeACwsLKBSPX52s1qtxpkzZyCTycr1xoGk7f/S/q9CI70HxQ8wL20eRr85WvJvEqniJFOKdnYdcO/e7gptQ6Mpeuml3x79ATQxManQPg2ZRqPRefG+yrafVkBOTk4AgBo1amDgwIE4evQo3n777bLn1qxZE3fv3i0rx4yMDNSpU+exbahUKoSGhiInJ+eV8wGQxBsGKe9DZJFoNBokXkh85kk1L+t67nVczbmKBtUaaCkZSZVkSrF+/c9x//5hqNUPyrkFOapXHwgzM3ut5jJmMpms7A+jFBUUPDxpwsrKCgCQnJyMjz766LHy7NOnD6KiojB48GBcv34dSqUS9evXf2w75ubmSEtLK1cGtVotiTcMf//46Li56JmGRx8f/TsSUepqUzXU1dRABXvZzMQMt/NvsxSNgGT+2tnbvwNTU1soleUrRbncEvXrf6blVCRlt27dwsCBA6HRaKBSqdC/f3/0798fK1asQElJCcaMGQNfX19s2bIFbdu2hUwmw7x582BhYaG1DHK5HHK5HGZmZlrbpiF5dJhC1KGJB6oHkN3XzkhVrVFrZTskbZK5eB8AsrLW4s8//wW1+tXOElOp5KhevQfatUvWUTKSqkdTvH8//llUVASNRgNLS0sAQG5uLu7ceXiiRYMGDXhcyIioNWqYzTKrcKFZm1njROgJNHVoqqVkJFWSOkvA0XE4nJ0nQi63funXyGSWyMmxxZQpKty/X7ETdUj/PJqaMzc3Lzs+bGFhUVaIwMMTsBo2bIiGDRuyEI2MXCZHF6cuFd6OnbkdGtvzjGVjIKlSBIBGjcLRqNFXkMstIZM9b5pLBrncBlWrdkW/flfRqFFL9OjRg9egEdFjJrtOhp25Xblfb2VqhU+7fMrFwo2EpKZP/66wMAPXrn2P69d/wMM7Zmig0aghk5lArVbCwcELzs6TULWqK2QyGTQaDcLDw7FmzRrs2rULjRo1Ev0lEJEElKhLUPvr2ridf7tcr7c0sUTmp5mobl1dy8lIiiRbio+o1Urk5OyHUnkLGo0Spqb2qFKlE8zNHZ/6/O+//x5fffUV4uPj0aZNm0pOS0RStOn3TRi5ZeQrLfMGADZmNpjcbTKmu03XUTKSGsmXYnnExMTgww8/xIYNG+Dm5iY6DhFJwLc/f4t/7/73SxejjZkNhrcejh99fuSxaCNikKUIALt378awYcOwbNky9O/fX3QcIpKAdafWIWRrCIoKi6Axe/qfPnOZOeQmckztPhVTu09lIRoZgy1FAPj111/Rr18/zJo1C6NGjRIdh4gkwL2nOxr1a4Q0WRoy72fCzMQMMsigUqtgpjZDzfM18fMPP8PByuHFGyODI5mL93Whffv22Lt3L7y8vHDr1i188cUXfNdHZMT27t2LjIsZSHo/6eGyf/czcDv/NtQaNewt7VHbsjacnZyR/2U+HJxYisbIoEeKj1y/fh29e/eGh4cHvvnmGy7iTGSk3N3dERQUhKCgoGc+Z8yYMWjcuDG++OKLygtGkmEU7VC3bl3s27cPv/76K0aOHAmlUik6EhFVsj179uDatWsYMWLEc58XGBiIqKgo3nPVSBlFKQJAtWrVsGvXLjx48AC+vr548KC8C48Tkb7RaDSYOXMmpk+f/sIF7rt27QqlUolffvmlktKRlBhNKQIP76awadMm1KtXD56enrh9u3wX8xKRfklJScHNmzcxfPjwFz5XJpMhICAAK1eurIRkJDVGcUzxSRqNBv/+978RGxuLxMTEf9xKiIgMh0ajQffu3fH+++/D39//pV5z+fJldOjQAZmZmVq9qwpJn1GNFB+RyWSYM2cOxo4di27duuH3338XHYmIdCQpKQl37tyBn5/fS7+mYcOGaNWqFeLj43WYjKTIKEvxkY8//hhz5sxBjx49cOjQIdFxiEjLHh1LnDFjRtldVF4Wp1CNk1FOnz4pISGh7BegT58+ouMQkZbs3LkTn376KU6dOvXKpXj//n3Ur18f586dQ82aNXWUkKTGqEeKj3h7e2Pbtm0ICQnBqlWrRMchIi14NEqcOXPmKxciAFSpUgU+Pj6Ijo7WQTqSKpZiqc6dO2PPnj2YNm0avv76a9FxiKiCEhISkJeXhyFDhpR7G5xCNT6cPn1CRkYGevXqhX79+mHu3LlcFo5ID2k0GnTs2BGff/55hUqxpKQEDRo0QGJiIlq1aqXFhCRVHCk+wdnZGfv378e+ffswatQoqFQq0ZGI6BVt374dRUVFGDx4cIW2Y2JighEjRiAqKkpLyUjqOFJ8hkfTLqampoiOjoa1tbXoSET0EjQaDd566y1MnToVgwYNqvD2fv/9d/Ts2RNXr14t17FJ0i8cKT6DjY0Ntm7diqpVq8LLywt3794VHYmIXkJcXBxKSkowYMAArWzvtddeQ926dZGcnKyV7ZG0sRSfw8zMDCtXrkTHjh3h5uaGa9euiY5ERM+h0WgQFhaGsLAwrd4NJzAwkCfcGAmW4gvI5XJ8/fXXGDFiBLp164Y///xTdCQieobY2FjIZDL0799fq9v18/NDfHw87t+/r9XtkvSwFF+CTCbD5MmTMX36dLi7u+Po0aOiIxHRE9RqddkoUdtnjdeoUQM9evTAhg0btLpdkh6W4isICQnBjz/+iL59+yIpKUl0HCL6m82bN8PMzAz9+vXTyfY5hWocePZpOezfvx/vvvsuvvvuO7z33nui4xAZPbVajbZt22Lu3Lno27evTvahVCpRr149HD58GI0bN9bJPkg8jhTLoXv37khOTsZnn32GxYsXi45DZPQ2btwIa2trna5dbG5uDj8/Py4FaeA4UqyAy5cvw8vLC35+fggPD+fqN0QClJSUoE2bNvjvf/8Lb29vne7rl19+wXvvvYfz58/z991AcaRYAQ0bNsSBAwcQHx+P0NBQlJSUiI5EZHQ2bNgAOzs79O7dW+f7at++PSwtLZGWlqbzfZEYLMUKqlWrFvbs2YMLFy5g6NChKCwsFB2JyGiUlJQgPDy80mZqZDIZT7gxcCxFLbCzs8OOHTtgamoKb29v5OTkiI5EZBTWr18PBwcHeHl5Vdo+/f39sWnTJhQUFFTaPqnysBS1xMLCAmvXrkWrVq3g7u6OrKws0ZGIDJpKparUUeIj9erVQ4cOHRAbG1tp+6TKw1LUIhMTEyxatAgDBw6Eq6srLl68KDoSkcFat24datWqBU9Pz0rfd2BgIO+cYaB49qmOLF26FLNmzcKOHTvwxhtviI5DZFBUKhVatmyJH3/8ER4eHpW+//z8fNSrVw9nzpxB3bp1K33/pDscKepIaGgoFi5cCC8vL6SmpoqOQ2RQ1qxZg7p166JHjx5C9m9tbY1BgwZhzZo1QvZPusORoo6lpKTAz88PS5cu1cq93YiMnUqlQosWLbB8+XK4u7sLy7Fv3z6MGzcOp06d4jWLBoQjRR3z8PDAzp07MX78eCxbtkx0HCK9t2rVKjg7OwstRADo1q0b8vLy8NtvvwnNQdrFkWIlOX/+PHr16oXg4GBMnTqV7yyJyqG4uBjNmzdHZGQk3NzcRMfBzJkzce/ePSxcuFB0FNISlmIlunHjBry9veHm5oZvv/1WqzdBJTIGy5cvR3R0NJKTk0VHAQBcuHABXbp0wbVr12BmZiY6DmkB/ypXojp16mDv3r04ceIE/P39oVQqRUci0htKpRJffvklwsPDRUcp06RJEzRv3hwJCQmio5CWsBQrWdWqVZGYmIjCwkL069cPDx48EB2JSC9ERkaiWbNmcHV1FR3lMQEBAVz2zYBw+lQQlUqF0NBQnDx5Ejt27EDNmjVFRyKSLKVSCRcXF0RHR6NLly6i4zwmJycHDRo0wMWLF+Hg4CA6DlUQR4qCmJqaYtmyZejZsye6deuGK1euiI5EJFkKhQItW7aUXCECD2d/vL29ER0dLToKaQFLUSCZTIbZs2fjgw8+QLdu3XD69GnRkYgkp6ioCLNnz5bUscQncQrVcLAUJWDChAmYN28ePD09eZ82oicsX74cbdq0QadOnURHeaaePXsiIyMDZ8+eFR2FKojHFCUkMTERI0aMQEREBHx8fETHIRKusLAQTZs2xZYtW9ChQwfRcZ5r0qRJMDMzw1dffSU6ClUAR4oS0qtXL+zYsQP/+te/OBVDBGDZsmVo166d5AsReDiFumrVKpSUlIiOQhVgKjoAPa5jx47Ys2cPevXqhVu3bmHSpEmiIxEJUVBQgLlz5yIuLk50lJfSunVr1KxZE3v27ME777wjOg6VE0eKEtSiRQukpaUhMjISkyZNglqtFh2JqNL99NNPeOutt9C+fXvRUV4a77Oo/3hMUcKys7Ph4+MDFxcXLF++nMtIkdHIz89HkyZNEB8fj3bt2omO89Ju3bqFZs2aISMjA3Z2dqLjUDlwpChhDg4OSE5Oxu3btzFw4EDk5+eLjkRUKZYuXYouXbroVSECQK1ateDm5oZNmzaJjkLlxFKUOGtra8TGxqJ69ep45513kJ2dLToSkU7l5eVh/vz5CAsLEx2lXDiFqt9YinrAzMwMERERcHV1Rffu3ZGZmSk6EpHO/PDDD3B1dUWbNm1ERykXHx8fnDx5kqtU6SkeU9Qz8+fPx5IlS7Bz5060aNFCdBwircrLy0OTJk2QlJSE1q1bi45TbuPGjUPdunUxbdo00VHoFXGkqGcmTZqEsLAwuLu748iRI6LjEGnVkiVL4ObmpteFCPxvCpVjDv3DkaKe2rZtG0JCQrBmzRp4eXmJjkNUYbm5uWjatClSUlLQqlUr0XEqRKPRoGXLloiIiJDkIub0bBwp6ql+/fohNjYWI0eOxLp160THIaqwxYsXw8PDQ+8LEXi42D8XCddPHCnqudOnT8Pb2xuTJk3ChAkTRMchKpf79++jadOm2Lt3L1q2bCk6jlZkZGTgjTfewLVr12BpaSk6Dr0kjhT13Ouvv44DBw5gyZIlmDp1Ko9hkF5atGgRevbsaTCFCADOzs5o164dtm3bJjoKvQKOFA3EX3/9hb59+6Jt27b44YcfYGrKZW1JP+Tk5KBp06Y4cOAAmjdvLjqOVq1atQrr16/H9u3bRUehl8RSNCAPHjzAoEGDYGNjg3Xr1nHKhvTCrFmzkJ6ejlWrVomOonUPHjyAs7Mzzp49C0dHR9Fx6CVw+tSA2NraYvv27bCwsEDv3r2Rk5MjOhLRc927dw8LFy7E9OnTRUfRCVtbW/Tv3x9r164VHYVeEkvRwJibm2Pt2rVo3bo13n77bdy4cUN0JKJn+vbbb+Hj44NmzZqJjqIzgYGBPAtVj3D61EBpNBrMnj0bERERSExMRNOmTUVHInrM3bt34eLigsOHD6NJkyai4+iMWq1Go0aNEBcXh7Zt24qOQy/AkaKBkslkmDZtGiZPngw3NzccO3ZMdCSixyxYsAC+vr4GXYgAIJfLMXLkSI4W9QRHikZg8+bNCA0NRXR0NDw8PETHIUJ2djZcXFxw9OhRNG7cWHQcnUtPT4ebmxsyMzN5ZrjEcaRoBAYNGoSYmBj4+fnxPm8kCd988w0GDhxoFIUIAM2aNUOjRo2QmJgoOgq9AEeKRuT48ePo27cvZsyYgbFjx4qOQ0bqzp07aNasGX799Vc0bNhQdJxKs3TpUqSkpCAmJkZ0FHoOlqKRuXDhAry8vBAYGIjp06dDJpOJjkRGZsqUKbhz5w5++ukn0VEq1d27d9GwYUNcvnwZ9vb2ouPQM7AUjdDNmzfh7e0NV1dXLFy4ECYmJqIjkZH466+/0KJFCxw7dgwNGjQQHafSDRkyBO+88w5naiSMxxSNUO3atZGamoozZ85g+PDhKCoqEh2JjMTKlSsxdOhQoyxEgNcs6gOOFI1YYWEh/P39kZOTgy1btsDOzk50JDJgGo0GhYWF0Gg0sLa2Fh1HiOLiYjg7O2P//v1wcXERHYeegiNFI2ZpaYmYmBg0adIEPXr0wP3790VHIgMmk8lgZWVltIUIAGZmZhg+fDiioqJER6Fn4EiRoNFosHbtWgwaNAhWVlZPfY5arYZczvdQ9Or4b+dxx48fR//+/XHp0iV+XySIPxGCTCaDv7//MwsReLja/4MHD7Br165KTEb6qLi4GCUlJTh37hwAlP3hV6vVImNJxhtvvIFq1aph3759oqPQU3CkSM9UVFSE+Ph4FBUVYcOGDahSpQqio6MRExODfv36iY5HEvXhhx/i9u3bMDMzw40bN+Dv74+goCDRsSTlm2++walTpxARESE6Cj2BpUhPdeDAAURGRqJatWp45513kJubi/T0dJw+fRrfffcdatasKToiSdDu3bsxceJEbN68GSqVCqdOncLSpUshk8kQHh6Ozp07Q6PRGP31sTdv3kTLli2RmZkJGxsb0XHobzh9Sk9la2uLpKQkNG3aFL1790ZWVhYOHz6M8PBw1KxZEyUlJaIjkgRlZmaic+fOaNSoEVxcXDBo0CDExcWhf//+ZUsMGnshAg8vi+ratSs2b94sOgo9gSNF+odH7+SPHz+OoUOHom3btlCr1Zg2bRratWuHkpISXvBPT3X79m0EBASga9eumDZtWtnn8/PzMXToUAQHB2Pw4MECE0pHTEwMli1bhqSkJNFR6G84UqR/ePRO/o033sD48eOxa9cu1K5dG+3atYNarS57/PLlyzhy5AgWLVqE7OxskZFJImrUqIE5c+Zg9+7daN++PRYvXgyNRoPi4mJcvHiR9/X8G19fXxw7dgwZGRmio9DfcKRIz5SamoqwsDCMGjUKcrkc/v7+UKlUMDU1xaFDhzB37lw4OjqisLAQv/76KxISElC/fn3RsUmgvx8vTExMxFdffYXs7Gx06tQJpqamWLp0qeCE0jJ27Fg0bNgQU6ZMER2FSrEU6bkOHjyIrl27Pva5M2fOYNiwYfj000/Rt29f1KxZE2PGjEHfvn3Rv39/QUlJtEeF+OR1ienp6XB0dIStrS2n3Z9w8OBBjBo1Cr///juPtUoEp0/pubp27Yp169aVnTqenZ2Njz76CCEhIQgKCio7CzUnJ0dkTJIAmUyGv7/HLi4uBvDwXoJVq1ZlIT5Fly5doFKpcPToUdFRqBRLkV5o2LBh8PT0BAAcOXIEzZs3R3BwcNnjU6ZMQXp6OkeJRurs2bNYvHgxDhw4AJlMVjZKNDMzAwDMmDEDhYWFIiNKlkwmQ0BAABcJlxCWIr2UR8cKr1+/DnNzc1StWhXAw4uQk5OTERsbC4CrlhibnTt3IiQkBBcuXEBgYCDCw8PLHispKUF+fj6aNGkCS0tLgSmlbeTIkVi/fj3vViMRLEV6JTVq1EBiYiKio6Pxn//8B9988w0UCgUaNGgAjUbDtRyNzJw5czBx4kQsWLAACQkJ+P3333H9+nUAgImJCaytrREYGCg4pbQ1bNgQrVu3xo4dO0RHIbAU6RX5+vpi5syZSElJgZmZGZKTk9G6dWuuUmKE/vjjDzg4OGDQoEHQaDRwcXGBg4MDtm7dCgCYN28eFi5cKDilfuAUqnTw7FOqsEdnGz66XIOMw927d3Hs2DF07Nix7F6caWlp+Pjjj7F//364ublBoVDg9ddfF5xU+nJzc+Hs7Ixz585xCUXBOFKkCpPL5VCr1bhw4QKWLFkiOg5VEnt7e3h6ej52c2pXV1e0bt0avr6+eOONN1iIL8nOzg79+vXDunXrREcxeixF0gq5XA4bGxssWrQIU6ZMAScgjIdKpQIAnD9/Hr///jvc3Nxw+PBhTJ48WXAy/cIpVGlgKZLWODk54cCBA0hJScHo0aPL/liSYXs0ZT569Gjs378ffn5+WLBgAZo0aSI4mX7x8PBAVlYWTp8+LTqKUWMpklbVqFEDu3fvxrVr1zB48GAUFBSIjkSV4PLly6hbty7Gjh0LS0tLhISEiI6kd0xMTDBy5EhERUWJjmLUeKIN6YRSqURQUBAyMzMRFxeHatWqiY5EOqRSqXDnzh04OjqiuLi47MJ9ejV//PEHPD09cfXqVZ60JghHiqQT5ubmWL16Nd588024ubmVXbtGhuXRYg2mpqZwdHQEABZiBbRs2RJOTk5ITk4WHcVosRRJZ+RyORYsWIBhw4bB1dUV6enpoiORlm3ZsgVKpVJ0DIMSGBjIKVSBOH1KlWL58uWYPn06tm/fjvbt24uOQ1rwxx9/4O2338b58+dRpUoV0XEMxp07d9CkSRNcuXKlbDlFqjwcKVKlGD16NH744Qd4e3tj9+7douOQFvznP//BJ598wkLUsurVq8PDwwMbNmwQHcUosRSp0gwYMAAbNmzAsGHD+Auv586cOYOUlBSMHz9edBSDFBgYyGsWBeH0KVW6EydOoE+fPpg6dSrGjRsnOg6Vw3vvvYc333yTF+jriFKphJOTEw4dOsTrPSsZS5GEuHjxInr16gV/f3/MnDmTi4nrkVOnTuGdd97BhQsXYGtrKzqOwZowYQIcHBwQFhYmOopRYSmSMFlZWfD29kanTp2wePFi3pldT7z77rvo3LkzJk6cKDqKQfv1118xZMgQnD9/nrdkq0T8TpMwjo6OSE1NRXp6Ovz8/HiTVT1w4sQJpKWl4f333xcdxeC9+eabsLa2RlpamugoRoWlSEJVqVIF8fHxAIA+ffrg/v37ghPR84SHh2PSpEmwsbERHcXgyWQynnAjAEuRhLOwsEB0dDSaNWuGHj16ICsrS3Qkeorjx4/j559/RmhoqOgoRsPf3x/nzp1DcXGx6ChGg8cUSTI0Gg3Cw8OxZs0a7Nq1C40aNRIdif5mwIABcHd3x8cffyw6ilEpLCyEubk5jytWEpYiSc7333+Pr776Cjt27EDbtm1FxyE8POnD19cX58+fh5WVleg4RDrDZdhJcsaNG4caNWqgZ8+e2LhxI9zc3ERHMnphYWGYPHkyC5EMHkeKJFm7d+/GsGHD8NNPP2HAgAGi4xito0ePYuDAgTh//jwsLS1FxyHSKY4USbI8PT2RkJAAHx8f3L59G6NHjxYdySiFhYVhypQpLETBeJ/KysEjtyRp7du3x969ezF79mzMmTMHnNioXIcPH8bJkyf5hkQCZsyYgbt37/7j8/yd0C6WIkles2bNkJaWhnXr1uGTTz4pu7Et6V5YWBj+/e9/w8LCQnQUo1VSUgIAuHHjBhYvXgwAKCoqwu3bt/Hzzz9j3bp1IuMZHB5TJL1x79499OvXD/Xr10dERATMzc1FRzJohw4dgp+fH9LT01mKEnD06FGkpaVhzJgx2LhxI44ePYqMjAzExcXhzz//hIuLi+iIBoGlSHqloKCgbEm4jRs3ckFqHfLy8sLgwYMxduxY0VGMXnJyMlxcXNCgQQMAgLu7O2rVqoWYmBiEhYWhpKQEs2bNEpzSMHD6lPSKlZUVNm3ahHr16sHT0xO3b98WHckgpaWlIT09HcHBwaKjEIBdu3YhLi6u7L/Hjh1bdnnM0KFDcfLkSVHRDA7+37APAAAZ/UlEQVRLkfSOqakpli9fDg8PD3Tv3h1Xr14VHcngzJw5E9OmTeMUtUR4e3tj69atZf9dtWpVODg4QKlU4rXXXsPHH3/MBfW1hNOnpNcWLFiABQsWICEhAa1atRIdxyDs378fgYGB+PPPP3kJgIS4urrC29sbV69exdatW7FixQr4+PiIjmVwOFIkvfbJJ5/gq6++goeHBw4dOiQ6jkF4NEpkIUrL+vXrYWZmBltbWyQnJ/+jEDm+0Q6OFMkgJCQkICAgACtXrkSfPn1Ex9FbqampGDVqFM6ePctSlDi1Ws1FwnWA31EyCN7e3ti2bRtCQkKwatUq0XH0kkajwcyZMzF9+nQWokSpVCpkZGQ89jmOa7SLpUgGo3PnztizZw+mTZuGr7/+WnQcvbNnzx5cv34dI0aMEB2FnmHjxo1Ys2YNAJSNEmUyGfLy8pCYmIicnByR8QwCp0/J4GRkZKBXr17w8fHBvHnzIJPJREeSPI1GAzc3N4wZMwYjR44UHYeeQaPRPPbved26dYiJiUFaWhrat2+P6tWro0uXLvjggw8EptRvHCmSwXF2dsb+/fuxf/9+hISEQKVSiY4kebt378atW7cwbNgw0VHoOR4V4qFDh9C6dWt888038Pb2xpUrV5CQkID3338fy5cvF5xSv7EUySBVr14dycnJuHnzJgYOHIj8/HzRkSTr0bHEGTNmwNSUN86ROqVSia1bt2LSpEk4evQoxowZAysrKyiVShQWFsLe3h5ZWVmiY+otliIZLBsbG8TFxaFq1arw8vJ66h0GCEhKSkJ2djb8/PxER6GXYG5ujo0bN8Ld3b3scyqVCgcPHkR0dDQmT54MR0dHnoBTTjymSAZPrVZj4sSJSEpKws6dO1GvXj3RkSRDo9GgS5cu+Oijjzh1qkc+//xznDlzBh4eHlCpVIiPj0dhYSECAgIQHBwMa2tr0RH1FkuRjIJGo8H//d//YenSpdi5cyeaN28uOpIkJCQk4LPPPsOpU6dgYmIiOg69pOzsbBw9ehSnT5/GjRs30LNnT/Tq1Ut0LIPAUiSjolAoMHXqVMTFxaFDhw6i4wil0WjQqVMnTJw4EUOHDhUdh8rhybNReUF/xfG7R0YlJCQEP/74I/r27YukpCTRcYSKj49HQUEB3n33XdFRqBweFaJGoyn7Hwux4vgdJKPj6+uLTZs2YcSIEYiOjhYdRwiNRoOwsDDMnDmTf0j11N9HiKdOncL58+cFpjEcPP+ajFL37t2RlJSEPn364K+//sKHH34oOlKl2r59O5RKJQYNGiQ6ClWQTCbDjh07cPnyZfz444+i4+g9HlMko3bp0iX06tULfn5+CA8PN4rVbzQaDdq3b49p06axFA1EZmYm2rRpg2vXrpXdfJjKh/MmZNQaNWqEAwcOID4+HqGhoSgpKREdSee2bt0KtVqNAQMGiI5CWuLk5IT27dtj27ZtoqPoPZYiGb1atWphz549uHDhAoYOHYrCwkLRkXRGrVYjLCwM4eHhPJZoYAIDA7Fy5UrRMfQefyuIANjZ2WHHjh0wNTWFt7e3wd5tIDY2FiYmJvD19RUdhbRs4MCBOHjwIG7evCk6il5jKRKVsrCwwNq1a9GqVSu4u7sb3B+XR6PEsLAwozh2amxsbGwwYMAArF27VnQUvcZSJPobExMTLFq0CAMHDkS3bt1w4cIF0ZG0ZvPmzbCwsICPj4/oKKQjnEKtOJYi0RNkMhlmzJiBiRMnonv37vjtt99ER6owjhKNg5ubG3JycnD8+HHRUfQWS5HoGUJDQ/Hdd9+hV69eSE1NFR2nQjZs2AAbGxv06dNHdBTSIblcjpEjRyIqKkp0FL3F6xSJXiAlJQV+fn5YunSpXl7XV1JSUnZD2t69e4uOQzp27tw5dO/eHRkZGTAzMxMdR+9wpEj0Ah4eHti5cyfGjx+PZcuWiY7zymJiYlC1alXeRcFIuLi4oHHjxkhMTBQdRS+xFIlewptvvol9+/Zh7ty5+PLLL/XmBq4lJSX4z3/+YzSr9dBDgYGBnEItJ06fEr2CGzduwNvbG927d8fChQslfwH8mjVr8P333+PAgQMsRSNy9+5dNGrUCJcuXYK9vb3oOHpF2r/RRBJTp04dpKam4uTJk/D394dSqRQd6ZlUKhVHiUbK3t4eXl5eWL9+vegoeoelSPSKqlWrhp07d6KwsBA+Pj7Izc0VHemp1q5di1q1asHT01N0FBKA1yyWD6dPicpJpVIhNDQUJ0+exI4dO1CzZk3RkcqoVCq0bNkSP/74Izw8PETHIQFUKhWcnJywb98+NGvWTHQcvcGRIlE5mZqaYtmyZejZsye6deuGK1euiI5UZvXq1ahXrx569OghOgoJYmpqCn9/f55w84o4UiTSgu+++w7z589HQkICXn/9daFZiouL0aJFCygUCrz99ttCs5BYJ06cgK+vLy5duiT5k8Kkgt8lIi2YMGEC5s2bB09PT6SlpQnNsmrVKjRo0ICFSGjbti3s7e2xd+9e0VH0BkuRSEuGDx+OqKgoDBgwANu3bxeSobi4GF9++SXCw8OF7J+khyfcvBpOnxJp2eHDh9G/f3/MnTsXQUFBlbrvZcuWYf369UhOTq7U/ZJ0ZWVloUWLFsjIyICtra3oOJLHkSKRlnXq1AmpqamYOXMm5s+fX2n7VSqVmD17NkeJ9BhHR0e4urpiy5YtoqPoBZYikQ60aNECaWlpiIyMxMSJE6FWq3W+z4iICDRv3hyurq463xfpF06hvjxOnxLpUHZ2Nnx8fODi4oLly5fr7K4FRUVFcHFxQUxMDDp37qyTfZD+KiwsRL169XD8+HE4OzuLjiNpHCkS6ZCDgwOSk5Nx+/ZtDBw4EPn5+TrZj0KhQKtWrViI9FSWlpYYMmQIVq1aJTqK5HGkSFQJiouLMXr0aJw7dw7bt2+Hg4OD1rZdWFgIFxcXbNq0CR07dtTadsmwHDp0CMHBwfjjjz+4Fu5zcKRIVAnMzMwQEREBV1dXdO/eHZmZmVrb9vLly9GmTRsWIj1X586doVarceTIEdFRJI2lSFRJ5HI55s+fj6CgILi6uuLs2bMV3mZhYSHmzJmDsLCwigckgyaTyRAQEMATbl6A06dEAkRGRuKLL77A1q1b0alTp3Jv57vvvkNSUhK2bdumxXRkqK5cuYL27dvj2rVrsLCwEB1HkjhSJBIgKCgIy5Ytg4+PDxITE8u1jYKCAsydO5fXJdJLa9CgAdq0aSNsxSV9wJEikUBpaWkYNGgQvv32WwwbNuwfjxcWAps2AWfOANnZgL094OICDBkCrFjxLVJTUxEbGysgOemryMhIbN68GXFxcaKjSBJLkUiw06dPw9vbG5MmTcKECRMAAJcuAQsXAitWPHzOgwf/e76NDaBWawCsxerVb2LQoJaVH5r0Vm5uLpydnZGeno5atWqJjiM5LEUiCbhy5Qq8vLzw7rvvokuXL+HnJ4NSCRQXP+9VKlhbm+KHH4CAgMpKSoYgICAA7du3x0cffSQ6iuTwmCKRBDRo0AAHDhzAhg0FGDBAiby8FxUiAJgiPx94/31AoaiMlGQoeBbqs3GkSCQRFy4AbdpokJ//6hdWW1kBe/cCHTroIBgZnJKSEjRs2BDx8fFo3bq16DiSwpEikUR8/TWgVJZvpZHCQuDLL7UciAyWiYkJRo4ciaioKNFRJIcjRSIJyMsDHB0ffiwvS0vg8uWH2yF6kbNnz8LDwwNXr16Fqamp6DiSwZEikQTExADaWI5y+fKKb4OMQ4sWLeDs7IykpCTRUSSFpUgkAcePP37ZRXkUFgK//KKdPGQcAgMDOYX6BJYikQTcuaOd7dy7p53tkHHw8/NDQkICcnJyREeRDJYikQRUraqd7djZaWc7ZBwcHBzg6emJmJgY0VEkg6VIJAHNmz+8rKIizMw0aNFCO3nIeHAK9XEsRSIJGD4cqOh54MXFRcjJmY8///xTO6HIKHh7e+PPP//EhQsXREeRBJYikQTUqAH4+ADyCvxGtmunRpUqt/D222/D1dUVK1asQG5urvZCkkEyMzPDsGHDOFosxesUiSTil1+At98G8vNf/bU2NsCGDYC3N1BcXIyEhAQoFAqkpqZi4MCBCAkJQbdu3SDTxnUfZHCOHTuGwYMH48KFC5BX5J2ZATDur55IQt56C5g9G7C2frXXWVsD48Y9LETg4Tt/X19fxMbG4uzZs2jVqhXGjh2LZs2aYc6cObh27Zr2w5Nea9euHWxtbXHgwAHRUYRjKRJJyMcfA+HhL1+M1tbABx8A8+Y9/fHatWtj4sSJOHPmDFatWoVLly6hdevW6NOnDzZu3IiioiLthSe9JZPJEBgYyEXCwelTIklKTQXCwoDDhwG1GlAq//eYqSlgZga8/jowY8bDY5GvIi8vD5s3b4ZCocDp06fh7++PkJAQtGnTRptfAumZGzdu4LXXXsO1a9dg/arTFQaEpUgkYZcuAUuXAseOATk5QJUqQMuWD6dLW2rh3sIXLlxAZGQkIiMj4ejoiJCQEAwbNgz29vYV3zjpHW9vb4wcORLDhw8XHUUYliIRoaSkBMnJyYiIiEBCQgL69OmDkJAQeHp6Gv2JF8YkOjoaERERSExMFB1FGJYiET0mOzsba9euhUKhwJ07dxAUFISgoCA0atRIdDTSsYKCAtSrVw+nTp1CvXr1RMcRgm8BiegxDg4OGD9+PI4dO4bY2FjcvXsXHTp0gKenJ9asWYOCggLREUlHrKysMHjwYKxZs0Z0FGE4UiSiFyosLERcXBwiIiJw+PBhDB06FCEhIejQoQOvfTQwBw4cwNixY3H69Gmj/NmyFInolWRkZCAqKgoKhQJWVlYICQnBiBEjUKtWLdHRSAs0Gg2aNm2K9evX46233hIdp9Jx+pSIXomzszOmTp2Kc+fOYcmSJThx4gSaNWuGQYMGYfv27VCpVKIjUgXIZDIEBAQY7bJvHCkSUYXdv38fMTExUCgUuHz5MkaOHIng4GC04G079NKlS5fQqVMnZGZmwtzcXHScSsWRIhFVWJUqVTB69GgcPHgQu3fvhkajgbu7Oxcm11ONGjVCy5YtER8fLzpKpeNIkYh0gguT67cVK1Zg+/bt2LJli+golYqlSEQ6l5WVhdWrV2PFihUoLi5GcHAwAgMDjfZaOH1w//591K9fH+fPn0eNGjVEx6k0nD4lIp1zdHTEZ599hjNnzmD16tW4cuUKFyaXuCpVqqBv376Ijo4WHaVScaRIRELk5+dj06ZNjy1MHhwcjLZt24qORqUSExMxbdo0HD16VHSUSsNSJCLhLl68iMjISERERMDR0RHBwcEYPnw4FyYXrKSkBPXr10dSUhJee+010XEqBUuRiCSjpKQEu3fvhkKhwM6dO+Ht7c2FyQWbPHkyZDIZ5s6dKzpKpWApEpEkcWFyaThz5gx69eqFK1euwMTERHQcneNbLyKSpL8vTL5161bcu3cPHTp0gIeHB1avXo38/HzREY1Cq1atULt2baSkpIiOUik4UiQivVFUVIS4uDgoFAouTF6JFi1ahMOHD2P16tWio+gcS5GI9NKjhckjIiJgaWnJhcl16Pbt22jatCmuXr2KKlWqiI6jU5w+JSK99PeFyb///nucPHmybGHyffv24Vnv9x99vqCgAAcPHkRkZCSUSmVlRtc7NWrUgLu7OzZu3Cg6is5xpEhEBuPRwuR16tRBr169YGpq+tjjGo0GMpkMubm5+OCDD2BmZobbt2/j7NmzmD59OkaMGCEoufRt2bIFCxcuRGpqqugoOsVSJCKjkpubi2+++QaFhYWYM2cOACA9PR0WFhZo0KAB1Go1L/94CqVSiXr16uHIkSMGfQYwf/JEZPAuXbqEpKQkAMDly5dx6tQp5OTkYMqUKTh79iyaNWuGBg0aAMA/CvHUqVOVnleKzM3N8d5772HVqlWio+gUS5GIDF5+fj6WLl2KNm3aYN26dbh69Sq6d+8Oe3t7fPnll8jOzi577qPJs7/++guzZs3C2LFj0bx5c3z//fei4ktGYGAgoqKinnm81hCYvvgpRET6rVWrVti0aRNu3LiBXbt2wdbWFsOGDQMAvP7667hy5QocHBwA/O+445w5c5CVlYWDBw8iNTUVy5cvx7hx40R+GcK99dZbMDc3x8GDB+Hq6io6jk5wpEhEBk+tVkOlUqFOnTq4d+9e2dmmx44dQ4cOHR4b+cjlcuTl5SE+Ph5Tp04FANSvXx9mZmY4ffq0kPxSIZPJEBAQgJUrV4qOojMcKRKRwZPL5WXHCjt37owJEyYgPT0dd+/eRZcuXdC4cWMAD08mMTc3x44dO1CnTp3HFsE+e/YsnJ2dheSXkhEjRqBNmzZYuHAhrKysRMfROpYiERmVTp06ISUlBRs2bECtWrXg5eUFU1NT3LhxA3Xq1AEAREVFoX///mWviY2NhbOzM6pWrWr0Z6c6OTnhrbfeQlxcHN577z3RcbTOeH+yRGS0bGxsEBQUhD59+sDU1BQXL17EJ598gqKiIqhUKtjZ2aFTp04AgCtXrmDXrl0ICQkBAC4nBxj0FCqvUyQiekJkZCRiYmIwfvx4bN26FVWqVMH8+fPLHs/NzcWCBQvQuHFjDBo0CNbW1gLTVr68vDw4OTnhjz/+QO3atUXH0SqTsLCwMNEhiIikpEmTJsjMzMTGjRvRu3dvhIaGwsLCouzMVHNzc2RnZ2PlypX49NNPcenSJdSqVQt169Y1ipGkubk50tPTcfPmTXTt2lV0HK3iSJGIqAIyMzMRFRUFhUJhVAuT7927Fx9++CFOnDhhUG8EWIpERFqg0Wiwf/9+KBQKxMbGokePHggJCYG3t/c/1mA1BGq1Go0bN8aWLVvQrl070XG0hqVIRKRljxYmVygUuHTpEgICAhAcHIwWLVqIjqZVM2bMKDu+aihYikREOnT27FlEREQgKioKjRs3RnBwMIYOHWoQ9yU8f/48XF1dkZmZCTMzM9FxtIKXZBAR6VCLFi0wb948XL16FV988QV27NiB+vXrIygo6Ln3fdQHTZs2RdOmTbFz507RUbSGI0UiokqWlZWF1atXQ6FQQKlUIjg4GAEBAXBychId7ZX99NNPSEpKwoYNG0RH0QqWIhGRIBqNBkePHoVCoUBMTAw6d+6M4OBg+Pr6wsLCQnS8l3Lv3j00bNgQFy9eLFtUXZ+xFImIJCA/Px+bN2+GQqHAqVOnMHz4cISEhKBt27aio73Qe++9B3d3d7z//vuio1QYjykSEUmAtbU1RowYgZSUFBw+fBhVq1ZFv3790L59eyxZsuSxez5KzaP7LBoCjhSJiCSqpKQEKSkpUCgUSEhIgLe3N0JCQuDh4QETExPR8cqoVCo4OzsjNTUVzZs3Fx2nQliKRER6IDs7G+vWrYNCocBff/2FoKAgBAUFld32SrSJEyfCwsICs2fPFh2lQliKRER65sSJE4iIiMCaNWvQunVrhISECF+Y/OTJk/Dx8cHly5f1+tZa+puciMhItW3bFt9++y0yMzMxbtw4rF27Fk5OTggNDcWRI0eEXPvYpk0bVK9eHampqZW+b23iSJGIyAD8fWFyCwuLsoXJHR0dKy3Dt99+i99++02v77XIUiQiMiAajQYHDhyAQqHAli1bKnVh8qysLDRv3hyZmZmwtbXV6b50haVIRGSgcnNzyxYmv3jxYqUsTN6vXz8MGTIEAQEBOtuHLvGYIhGRgbKzs8OoUaOQlpaGPXv2AAB69OiBrl27Yvny5bh//77W9xkYGMjpUyIi0g8qlQo7d+6EQqFASkoKBgwYgJCQEHTv3l0rNwsuLCxEvXr18Ntvv6F+/fpaSFy5WIpEREbq1q1bWL16NVasWKHVhcnHjR0L9/x8DL13D8jIAJRKoFo1oGdPIDQUqFNHS1+B9rEUiYiM3JMLk3fq1AkhISGvvjB5URHw3/+ieP58FN2/D9sn68XS8uFHT09g9mxAguu6shSJiKhMfn4+tmzZAoVCgZMnT778wuT37gFeXsDp00BBwfOfK5MBVlbAunWAr6/2wmsBS5GIiJ7q0qVLiIyMREREBGrWrIng4GAMHz78n7eIKiwEunYFzpx5OFX6sqysgG3bHo4cJYKlSEREz/XkwuS9e/dGSEgIPD09Hy5M/tFHwLJlLx4hPo2tLXDtGlClivaDlwNLkYiIXtrdu3fLFia/desW/uXvj6kLF0JenkIEABsbYO5cYPx47QYtJ5YiERGVy4kTJ/D7xInol5yMCq1fU78+cPnyw2ONgvHifSIiKpe2bdti2K1bFStEAMjOBo4c0UakCmMpEhFR+V27VvFtyOXA1asV344WsBSJiKj8iooqvg21GsjPr/h2tIClSERE5aeNGxvL5UDVqhXfjhawFImIqPy0sSqNUgm0bl3x7WgBS5GIiMpv4sSH1xpWRLt2QJMm2slTQSxFIiIqv3feAezsyv96Oztg8mTt5akgliIREZWfXA7MmlW+Y4smJkDNmkDfvtrPVU4sRSIiqphRo4CgoFcrRrn84e2kUlMBU1NdJXtlLEUiIqq4xYuBCRMeFqP8BdViYwM4OQG//AI4O1dOvpfEZd6IiEh7fvkF+O9/ga1bH06PFhQ8vA7R3BwwMwNq1354DNHfXzuXc2gZS5GIiLQvOxvYsgW4efPhraXs7R/eXqpTJ0mscfosLEUiIqJSPKZIRERUiqVIRERUiqVIRERUiqVIRERUiqVIRERUiqVIRERUiqVIRERUiqVIRERUiqVIRERUiqVIRERUiqVIRERUiqVIRERUiqVIRERUiqVIRERUiqVIRERUiqVIRERUiqVIRERUiqVIRERUiqVIRERUiqVIRERUiqVIRERUiqVIRERUiqVIRERU6v8BNBdL57zpNjUAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7fb21fb61518>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "G = nx.from_numpy_matrix(w)\n",
    "layout = nx.random_layout(G, seed=10)\n",
    "colors = ['r', 'g', 'b', 'y']\n",
    "nx.draw(G, layout, node_color=colors)\n",
    "labels = nx.get_edge_attributes(G, 'weight')\n",
    "nx.draw_networkx_edge_labels(G, pos=layout, edge_labels=labels);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The brute-force method is as follows. Basically, we exhaustively try all the binary assignments. In each binary assignment, the entry of a vertex is either 0 (meaning the vertex is in the first partition) or 1 (meaning the vertex is in the second partition). We print the binary assignment that satisfies the definition of the graph partition and corresponds to the minimal number of crossing edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Objective value computed by the brute-force method is 3\n"
     ]
    }
   ],
   "source": [
    "def brute_force():\n",
    "    # use the brute-force way to generate the oracle\n",
    "    def bitfield(n, L):\n",
    "        result = np.binary_repr(n, L)\n",
    "        return [int(digit) for digit in result]  # [2:] to chop off the \"0b\" part\n",
    "\n",
    "    L = num_nodes\n",
    "    max = 2**L\n",
    "    minimal_v = np.inf\n",
    "    for i in range(max):\n",
    "        cur = bitfield(i, L)\n",
    "\n",
    "        how_many_nonzero = np.count_nonzero(cur)\n",
    "        if how_many_nonzero * 2 != L:  # not balanced\n",
    "            continue\n",
    "\n",
    "        cur_v = graph_partition.objective_value(np.array(cur), w)\n",
    "        if cur_v < minimal_v:\n",
    "            minimal_v = cur_v\n",
    "    return minimal_v\n",
    "\n",
    "sol = brute_force()\n",
    "print(f'Objective value computed by the brute-force method is {sol}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The graph partition problem can be converted to an Ising Hamiltonian. Qiskit has different capabilities in the Optimization module to do this. Here, since the goal is to show QAOA, the module is used without further explanation to create the operator. The paper [Ising formulations of many NP problems](https://arxiv.org/abs/1302.5843) may be of interest if you would like to understand the technique further."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "qubit_op, offset = graph_partition.get_operator(w)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So lets use the QAOA algorithm to find the solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0. 0. 1. 1.]\n",
      "Objective value computed by QAOA is 3.0\n"
     ]
    }
   ],
   "source": [
    "from qiskit.aqua import aqua_globals\n",
    "from qiskit.aqua.algorithms import QAOA\n",
    "from qiskit.aqua.components.optimizers import COBYLA\n",
    "from qiskit.circuit.library import TwoLocal\n",
    "\n",
    "aqua_globals.random_seed = 10598\n",
    "\n",
    "optimizer = COBYLA()\n",
    "qaoa = QAOA(qubit_op, optimizer, quantum_instance=BasicAer.get_backend('statevector_simulator'))\n",
    "\n",
    "result = qaoa.compute_minimum_eigenvalue()\n",
    "\n",
    "x = sample_most_likely(result.eigenstate)\n",
    "ising_sol = graph_partition.get_graph_solution(x)\n",
    "\n",
    "print(ising_sol)\n",
    "print(f'Objective value computed by QAOA is {graph_partition.objective_value(x, w)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The outcome can be seen to match to the value computed above by brute force. But we can also use the classical `NumPyMinimumEigensolver` to do the computation, which may be useful as a reference without doing things by brute force."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0 0 1 1]\n",
      "Objective value computed by the NumPyMinimumEigensolver is 3\n"
     ]
    }
   ],
   "source": [
    "npme = NumPyMinimumEigensolver(qubit_op)\n",
    "result = npme.compute_minimum_eigenvalue()\n",
    "\n",
    "x = sample_most_likely(result.eigenstate)\n",
    "ising_sol = graph_partition.get_graph_solution(x)\n",
    "\n",
    "print(ising_sol)\n",
    "print(f'Objective value computed by the NumPyMinimumEigensolver is {graph_partition.objective_value(x, w)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is also possible to use VQE as is shown below"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0. 1. 0. 1.]\n",
      "Objective value computed by VQE is 3.0\n"
     ]
    }
   ],
   "source": [
    "from qiskit.aqua.algorithms import VQE\n",
    "from qiskit.circuit.library import TwoLocal\n",
    "\n",
    "aqua_globals.random_seed = 10598\n",
    "\n",
    "optimizer = COBYLA()\n",
    "var_form = TwoLocal(qubit_op.num_qubits, 'ry', 'cz', reps=5, entanglement='linear')\n",
    "vqe = VQE(qubit_op, var_form, optimizer, quantum_instance=BasicAer.get_backend('statevector_simulator'))\n",
    "\n",
    "result = vqe.compute_minimum_eigenvalue()\n",
    "\n",
    "x = sample_most_likely(result.eigenstate)\n",
    "ising_sol = graph_partition.get_graph_solution(x)\n",
    "\n",
    "print(ising_sol)\n",
    "print(f'Objective value computed by VQE is {graph_partition.objective_value(x, w)}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<h3>Version Information</h3><table><tr><th>Qiskit Software</th><th>Version</th></tr><tr><td>Qiskit</td><td>0.23.0</td></tr><tr><td>Terra</td><td>0.16.0</td></tr><tr><td>Aer</td><td>0.7.0</td></tr><tr><td>Ignis</td><td>0.5.0</td></tr><tr><td>Aqua</td><td>0.8.0</td></tr><tr><td>IBM Q Provider</td><td>0.11.0</td></tr><tr><th>System information</th></tr><tr><td>Python</td><td>3.6.1 |Continuum Analytics, Inc.| (default, May 11 2017, 13:09:58) \n",
       "[GCC 4.4.7 20120313 (Red Hat 4.4.7-1)]</td></tr><tr><td>OS</td><td>Linux</td></tr><tr><td>CPUs</td><td>1</td></tr><tr><td>Memory (Gb)</td><td>5.827335357666016</td></tr><tr><td colspan='2'>Sun Nov 08 19:24:06 2020 EST</td></tr></table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<div style='width: 100%; background-color:#d5d9e0;padding-left: 10px; padding-bottom: 10px; padding-right: 10px; padding-top: 5px'><h3>This code is a part of Qiskit</h3><p>&copy; Copyright IBM 2017, 2020.</p><p>This code is licensed under the Apache License, Version 2.0. You may<br>obtain a copy of this license in the LICENSE.txt file in the root directory<br> of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.<p>Any modifications or derivative works of this code must retain this<br>copyright notice, and modified files need to carry a notice indicating<br>that they have been altered from the originals.</p></div>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import qiskit.tools.jupyter\n",
    "%qiskit_version_table\n",
    "%qiskit_copyright"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
